package william.basicsort;

import william.utils.ArrayUtils;

import java.util.Arrays;

/**
 * @author ZhangShenao
 * @date 2024/1/17
 * @description 插入排序
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArray(20, -100, 100);
        System.out.println("原始数组为: ");
        System.out.println(Arrays.toString(arr));
        InsertionSort insertionSort = new InsertionSort();
        insertionSort.insertionSort(arr);
        System.out.println("排序后数组为: ");
        System.out.println(Arrays.toString(arr));
        System.out.println("数组是否按照升序排列: " + ArrayUtils.isInAscOrder(arr));
    }

    /**
     * 假设数组前半部分已经有序
     * 针对无序部分的首个元素,向前逐个比较元素。如果当前元素比前面元素小,则进行交换
     * <p>
     * 插入排序的优点:与数据状况有关，如果元素数据近乎有序,则插入排序的效率很高。
     * <p>
     * 最好情况时间复杂度:O(N)
     * 最坏情况时间复杂度:O(N*N)
     */
    public void insertionSort(int[] arr) {
        //边界条件校验
        if (arr == null || arr.length == 0) {
            return;
        }

        //数组[0]位置已经有序,从第1个元素开始向前插入
        for (int i = 1; i < arr.length; i++) {
            //将当前元素逐个与前面元素进行比较,如果当前元素比前面元素小,则进行交换
            for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) {
                ArrayUtils.swap(arr, j, j - 1);
            }
        }
    }
}
